"Déjà Vu" bị rò rỉ trên mạng vào ngày 13 tháng 6 năm 2006.[10] Vào ngày 24 tháng 6 năm 2006, ca khúc đã được phát hành tại những đài phát thanh ở Mỹ,[11] 4 tuần sau khi Knowles thông báo rằng Columbia, hãng thu âm của cô, rằng B'Day đã hoàn tất. Hơn một tháng sau, ca khúc đã được phát hành dưới định dạng vật chất; ca khúc đã được phát hành ở dạng đĩa đơn CD vào ngày 31 tháng 7 năm 2006 tại Mỹ.[12] Một CD tăng cường sau đó được phát hành vào ngày 12 tháng 9, gồm 5 ca khúc kèm theo bản "Déjà Vu" đa phương tiện được bổ sung.[13][14] Ở Anh, phiên bản tải kỹ thuật số được phát hành vào ngày 15 tháng 8 năm 2006.[15] Một CD maxi và một đĩa đơn 12" tiếp tục được phát hành vào ngày 21 tháng 8 năm 2006.[16]Knowles sau đó đã hợp tác với đội ngũ sản xuất người Anh, Freemasons để phối lại ca khúc "Déjà Vu". Phiên bản câu lạc bộ đã được thực hiện và xuất hiện trong Đĩa mở động Freemasons của Green Light, phát hành ngày 31 tháng 7 năm 2007.[17] Một đĩa đơn maxi, gồm phiên bản album của ca khúc và bản phối câu lạc bộ của Freemasons đã được phát hành ngày 5 tháng 8 năm 2006 ở các nước châu Âu.[18]

Đánh giá chuyên môn

"Déjà Vu" từ khi ra mắt đã nhận được những đánh giá khen chê khác nhau từ những nhà phê bình âm nhạc. Joseph Mike từ trang tạp chí trực tuyến quốc tế PopMatters' tin rằng "thật tuyệt vời khi nghe Beyoncé hát giai điệu mạnh mẽ bằng phổi của mình cùng những dụng cụ nhạc trực tiếp."[19] Spence D. từ IGN Music, một trang tin tức đa phương tiện cùng nhiều bài đánh giá, khen ngợi giai điệu đầy âm bass của Jerkins, cho rằng nó đã mang cho ca khúc "sự hoàn hảo".[20] Mô tả "Déjà Vu" là một ca khúc "lộng lẫy", Caroline Sullivan từ The Guardian khen ngợi phần hợp tác giữa Knowles và Jay-Z và gọi đó là "sự kích thích lành mạnh của dòng nhạc pop". Cô còn nói thêm rằng dù Jay-Z không xuất hiện trực tiếp, nhưng anh vẫn mang đến sự dữ dội trong Knowles, khiến ta gợi nhớ đến "Tina Turner hoang dã khi trẻ."[3] Bernard Zuel của The Sydney Morning Herald khen ngợi sự quyết đoán khi Knowles hát ca khúc và cho rằng việc mua "Déjà Vu" rất "đáng giá."[21]

Một số nhà phê bình khác đã so sánh "Déjà Vu" với Đĩa đơn 2003 của Knowles, "Crazy in Love", đĩa đơn dẫn đầu của album đầu tay của cô. Theo Gail Mitchell của Billboard, ca khúc được xem như phần tiếp theo của "Crazy in Love".[22] Jason King của tạp chí Vibe xem bài hát là "nhân bản vô tính từ ADN giọng khàn của 'Crazy in Love'", trong khi đó, Thomas Inskeep từ tạp chí Stylus gọi ca khúc là "phiên bản nhẹ nhàng của 'Crazy in Love'";[23][24] dù vậy, có một vài nhà phê bình đánh giá khá tiêu cực khi họ phát hiện nhiều điểm tương đồng giữa hai bài hát. Trong bài đánh giá của Andy Kellman cho Allmusic, một cơ sở dữ liệu âm nhạc trực tuyến, anh cho rằng bài hát "có sự mạnh mẽ khiến ca khúc không trở nên phi thường như 'Crazy in Love'"[25] và đề cập về sự thành công trong mặt thương mại vào năm 2003. Phóng viên của trang báo trực tuyến Pitchfork Media, Ryan Dombal cho rằng "lần này [Knowles] bị đánh bật bởi những giai điệu mạnh mẽ".[26]

Sasha Frere-Jones từ tạp chí The New Yorker cho rằng lời nhạc của bài hát làm "rối loạn trí óc",[27] trong khi đó Chris Richards của The Washington Post, cho rằng nhân vật Knowles trong "Déjà Vu" là "một cô bạn gái bị điên vì yêu".[28] Jody Rosen của tờ Entertainment Weekly cho rằng việc lựa chọn "Déjà Vu" làm đĩa đơn dẫn đầu là một lựa chọn "buồn tẻ đến quái gở".[29] Ngược lại, Jaime Gill của Yahoo! Music cho rằng việc lựa chọn "Déjà Vu" làm đĩa đơn rất đúng đắn nhưng kết luận rằng ca khúc thiếu "kiểu điệp khúc chết người" và đề nghị Knowles nên bước thêm bước nữa để "thống trị toàn cầu."[30] Mặt khác, Jon Pareles của The New York Times viết rằng sự xuất hiện của Jay-Z "bình tĩnh thể hiện hơn bao giờ hết", nhưng trong ca khúc, anh chỉ làm cho Knowles "nghe không an toàn."[31]

Giải thưởng và đề cử

"Déjà Vu" đã được đề cử cho hạng mục Hợp tác rap/hát hiệu quả nhất và Bài hát R&B xuất sắc nhất tại Giải thưởng Grammy năm 2007, trong khi đó bản phối lại của ca khúc được đề cử trong hạng mục Bản thu phối khí xuất sắc nhất, Không cổ điển.[32] Ca khúc sau đó đã thắng hạng mục "Ca khúc xuất sắc nhất" tại giải MOBO ở Anh.[33] Năm sau đó, "Déjà Vu" đã nhận hai đề cử gồm "Ca khúc nhạc nhảy R&B/Urban xuất sắc" và "Ca khúc nhạc nhảy Pop xuất sắc" tại Lễ trao giải nhạc Nhảy Quốc tế thường niên lần thứ 22 năm 2007.[34] Ca khúc đồng thời còn được đề cử cho hạng mục "Hợp tác xuất sắc nhất" chung với "Upgrade U", một bài hát khác của Knowles kết hợp với Jay-Z, tại lễ trao giải Black Entertainment Television (BET).[35]

Diễn biến trên bảng xếp hạng

"Déjà Vu" xuất hiện trên bảng xếp hạng Billboard Hot 100 với vị trí 44, trước hơn một tháng trước khi ca khúc phát hành vật chất. Sau khi phát hành dưới dạng điện tử, ca khúc đã tiêu thụ được 75,000 bản kỹ thuật số trong tuần đầu phát hành.[36] Khiến bài hát tăng vọt lên vị trí thứ 4 trên bảng xếp hạng Hot 100.[37][38] Bản phối Freemasons/M. Joshua thì leo lên dẫn đầu bảng Billboard Hot Dance Club Play, trong khi phiên bản của album nằm tại vị trí 18 trên bảng xếp hạng này.[39] "Déjà Vu" còn vươn lên đứng nhất trên bảng xếp hạng Hot Dance Singles Sales và Hot R&B/Hip-Hop Songs, vị trí thứ 9 trên bảng Rhythmic Top 40 và vị trí 40 trên bảng xếp hạng Top 40 Mainstream.[39] Trong số cuối năm 2007 của Billboard, "Déjà Vu" đã xuất hiện tại vị trí thứ 7 trên bảng xếp hạng Hot Dance Singles Sales.[40]

"Déjà Vu" đồng thời còn vươn lên tốp 10 ít hơn 10 quốc gia ở châu Âu.[41] Với 29,365 bản được bán trong tuần đầu tiên,[42] đĩa đơn đã giành được vị trí đầu bảng trên bảng xếp hạng UK Singles Chart, trở thành đĩa đơn solo quán quân thứ hai của Knowles tại Anh.[43] Ca khúc đồng thời còn vươn lên tốp 5 tại Hungary, Ireland, Ý, Na Uy, Thụy Sĩ và nằm trong tốp 10 tại Bỉ, Phần Lan và Đức. Dù vậy, "Déjà Vu" lại không vươn lên được tốp 10 ở các nước châu Đại Dương. Đĩa đơn đạt được vị trí thứ 12 trên bảng xếp hạng Australian Singles Chart và vị trí thứ 15 trên bảng xếp hạng New Zealand Singles Chart.[41] "Déjà Vu" sau đó tiếp tục trở thành đĩa đơn bán chạy thứ 98 tại Úc năm 2006.[44] Ca khúc đồng thời còn nắm giữ kỷ lục về doanh số bán nhạc chuông tại Nhật Bản.[45]